package com.leetcode.tree;

/**
 * 找到中间的节点作为根节点，在递归的将左边左子树，右边作为又子树
 */
public class Leetcode109 {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null)
            return null;

        ListNode mid = findMidNode(head);
        TreeNode root = new TreeNode(mid.val);
        if (mid == head)
            return root;
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(mid.next);
        return root;
    }

    private ListNode findMidNode(ListNode head) {
        ListNode preMidNode = null;
        ListNode slowPtr = head;
        ListNode fastPtr = head;

        while (fastPtr != null && fastPtr.next!= null) {
            preMidNode = slowPtr;
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
        }

        if (preMidNode != null) {
            preMidNode.next = null;
        }

        return slowPtr;
    }

    public static void main(String[] args) {
        ListNode n1 = new ListNode(-10);
        ListNode n2 = new ListNode(-3);
        ListNode n3 = new ListNode(0);
        ListNode n4 = new ListNode(5);
        ListNode n5 = new ListNode(9);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        Leetcode109 leet = new Leetcode109();
        leet.sortedListToBST(n1);
    }

}
